package no.uio.ifi.cop.prover.hrete;

import java.util.LinkedList;
import java.util.HashMap;
import java.util.TreeSet;

import java.util.Comparator;

import no.uio.ifi.cop.common.Log;
import no.uio.ifi.cop.prover.RuleFinder;
import no.uio.ifi.cop.cl.Axiom;
import no.uio.ifi.cop.cl.Conjunction;
import no.uio.ifi.cop.cl.Predicate;
import no.uio.ifi.cop.cl.Term;
import no.uio.ifi.cop.cl.Substitution;
import no.uio.ifi.cop.util.Tuple;

import no.uio.ifi.cop.prover.RuleMatcher;

import no.uio.ifi.cop.prover.rete.MatchList;
import no.uio.ifi.cop.prover.rete.AlphaNode;
import no.uio.ifi.cop.prover.rete.BetaNode;
import no.uio.ifi.cop.prover.rete.ReteRuleMatcher;

/**
 *
 * An implementation of the RuleFinder interface which
 * uses the RETE algorithm.
 *
 * NOTE: This is the actual RETE algorithm, the other one
 * is just an imposter, a bastard if you will :-)
 *
 *
 * @version 1.0
 * @author  bjarneh@ifi.uio.no
 */

public final class HReteRuleFinder implements RuleFinder, Cloneable{

    static boolean stopped;

    LinkedList<MatchList> matches;
    HashMap<Integer, ReteRuleMatcher> lookUp;
    HashMap<String, AlphaNode> nodes;


    public HReteRuleFinder(boolean restart){
        nodes = new HashMap<String, AlphaNode>();
        lookUp = new HashMap<Integer, ReteRuleMatcher>();
        matches = new LinkedList<MatchList>();
        stopped = false;
    }

    public HReteRuleFinder(){
        this(true);
    }

    // to clone the HReteRuleFinder
    private HReteRuleFinder(HashMap<Integer, ReteRuleMatcher> cloneLookUp,
                           HashMap<String, AlphaNode> cloneNodes,
                           LinkedList<MatchList> cloneMatches){
        // we are the clones
        lookUp  = cloneLookUp;
        nodes   = cloneNodes;
        matches = cloneMatches;
    }

    public Tuple<Axiom, Substitution> getNextMatch(){

        if( matches.isEmpty() ){ return null; }

        MatchList current;
        Substitution subst;
        Axiom ax;
        ReteRuleMatcher rlmatcher = null;
        Tuple<Axiom, Substitution> pair = null;
        
        do{

            current = matches.peek();

            rlmatcher = lookUp.get( current.getId() );
            rlmatcher.addMatchList( current );

            if( ! rlmatcher.exhausted() ){
///  this statement 
///  subst = rlmatcher.poll();
///  has been replaced by the following section
                subst = rlmatcher.peek();
                if( ! rlmatcher.cacheAdvance() ){
                    matches.poll();
                }

                ax    = rlmatcher.getAxiom();
                pair  = new Tuple<Axiom, Substitution>(ax, subst);
                rlmatcher.clearQueue();
                break;
            }else{
                rlmatcher.clearQueue();
                matches.poll(); // disgard
                if( matches.isEmpty() ){
                    break;
                }
            }


        }while(! matches.isEmpty());
        
        return pair;
    }

    @SuppressWarnings("unchecked")
    public void addRule(Axiom ax){

        AlphaNode tmpAlpha;
        String    tmpKey;
        int ruleMatcherId;

        // add alpha node if not present for predicates

        for( Term t : ax.getLHS() ){

            tmpKey   = t.toString();
            tmpAlpha = new AlphaNode((Predicate) t);

            if( ! nodes.containsKey( tmpKey ) ){
                nodes.put( tmpKey,  tmpAlpha );
            }
        }

        // NOTE: a pointer from last beta-node to this instance
        ReteRuleMatcher rrmatch = new ReteRuleMatcher( ax );
        ruleMatcherId = rrmatch.getId();
        lookUp.put( ruleMatcherId, rrmatch );


        // construct beta nodes (tree) for each rule

        AlphaNode currentAlpha;
        // set these to null to please the compiler
        BetaNode prevBeta = null, currentBeta = null;

        for( Term t : ax.getLHS() ){
            
            currentAlpha = nodes.get( t.toString() );

            if( currentAlpha == null ){
                Log.fatal("currentAlpha is null?");
            }

            currentBeta = currentAlpha.getBeta(ruleMatcherId);

            if( prevBeta != null ){
                currentBeta.addParent( prevBeta );
            }

            prevBeta    = currentBeta;
        }

        // add pointer to axiom and last beta node
        if( currentBeta != null ){
            rrmatch.addBeta( currentBeta );
        }else{
            Log.fatal("currentBeta is null?");
        }

    }

    public void addPredicate(Predicate p){

        LinkedList<MatchList> tmp;
        ReteRuleMatcher matchedRule;

        for(AlphaNode alpha: nodes.values()){
            tmp = alpha.match( p );
            if( tmp.size() > 0 ){
                matches.addAll( tmp );
            }
        }
    }


    public boolean exhausted(){
        if( stopped ) { return true; }
        return (matches.size() == 0);
    }


    public RuleFinder clone(){

        ReteRuleMatcher tmp;

        LinkedList<MatchList> copyMatches;
        HashMap<Integer, ReteRuleMatcher> copyLookUp;
        
        // the tricky part is doing this the wrong way around..
        HashMap<String, AlphaNode> copyNodes  = new HashMap<String, AlphaNode>();

        for( String key : nodes.keySet() ){
            copyNodes.put( key, nodes.get(key).clone() );
        }

        copyLookUp = new HashMap<Integer, ReteRuleMatcher>();

        for( ReteRuleMatcher rule : lookUp.values() ){
            tmp = rule.clone();
            tmp.addAlpha( copyNodes );
            copyLookUp.put( rule.getId(), tmp );
        }

        copyMatches = new LinkedList<MatchList>();

        for( MatchList ml : matches ){
            copyMatches.addLast( ml.clone() );
        }

        return new HReteRuleFinder( copyLookUp, copyNodes, copyMatches );
    }

    public void stop(){
        stopped = true;
    }

    public String toString(){
        StringBuilder sb = new StringBuilder();
        for( ReteRuleMatcher rule : lookUp.values() ){
            sb.append( rule.infoString() );
        }
        return sb.toString();
    }
}
